#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;

typedef int Vertex; /* 顶点编号类型 */
typedef int GElemSet; /* 边权重类型 */
typedef char VertInfo; /* 顶点信息类型 */

typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest; /* 边的另一端点编号 */
    GElemSet weight; /* 权重 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj; /* 邻接表头指针 */
    VertInfo data; /* 存储顶点信息 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed; /* true为有向图，false为无向图 */
};
#define NIL -1 /* 顶点不存在时的返回值 */

void InitGraph(LGraph graph, int kMaxVertex, bool directed);
Vertex FirstAdjVert(LGraph graph, Vertex v);
bool ExistEdge(LGraph graph, Vertex u, Vertex v);
void InsertEdge(LGraph graph, Vertex u, Vertex v, GElemSet weight);
void RemoveVert(LGraph graph, Vertex v);

LGraph BuildGraph() {
    LGraph graph;
    int kMaxVertex, n, m, i;
    Vertex u, v;
    GElemSet weight;

    scanf("%d\n", &kMaxVertex);
    graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(graph, kMaxVertex, true);
    scanf("%d %d\n", &n, &m);
    for (v = 0; v < n; v++) {
        scanf("%c ", &graph->ver_list[v]->data);
        graph->n_verts++;
    }
    for (i = 0; i < m; i++) {
        scanf("%d %d %d\n", &u, &v, &weight);
        InsertEdge(graph, u, v, weight);
    }
    return graph;
}

int main(void) {
    LGraph graph;
    Vertex u, v;
    Position p;

    graph = BuildGraph();
    printf("邻接表为：\n");
    for (v = 0; v < graph->n_verts; v++) {
        printf("list[%d]->", v);
        p = graph->ver_list[v]->adj;
        while (p != NULL) {
            printf("%d:%d->", p->dest, p->weight);
            p = p->next;
        }
        printf("end\n");
    }
    printf("顶点数 = %d\n", graph->n_verts);
    scanf("%d %d\n", &u, &v);
    printf("<%d, %d> 的存在性 = %d\n", u, v, ExistEdge(graph, u, v));
    scanf("%d %d\n", &u, &v);
    printf("<%d, %d> 的存在性 = %d\n", u, v, ExistEdge(graph, u, v));
    scanf("%d\n", &v);
    printf("顶点%d的第一个邻接点 = %d\n", v, FirstAdjVert(graph, v));
    scanf("%d\n", &v);
    printf("待删除的顶点信息为 %c\n", graph->ver_list[v]->data);
    RemoveVert(graph, v);
    printf("当前顶点数 = %d\n", graph->n_verts);
    printf("当前边数 = %d\n", graph->m_edges);
    for (v = 0; v < graph->n_verts; v++) {
        printf("%c", graph->ver_list[v]->data);
    }
    printf("\n");
    printf("邻接表为：\n");
    for (v = 0; v < graph->n_verts; v++) {
        printf("list[%d]->", v);
        p = graph->ver_list[v]->adj;
        while (p != NULL) {
            printf("%d:%d->", p->dest, p->weight);
            p = p->next;
        }
        printf("end\n");
    }
    return 0;
}

void InitGraph(LGraph graph, int kMaxVertex, bool directed) {
    /* 初始化一个空的图 */
    Vertex v;
    Position p;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明邻接表头结点数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (AdjList *)malloc(sizeof(AdjList) * kMaxVertex);
    for (v = 0; v < kMaxVertex; v++) {
        graph->ver_list[v] = (AdjList)malloc(sizeof(struct HeadNode));
        graph->ver_list[v]->adj = NULL;
    }
    graph->directed = directed;
}

/* 算法7-7: 返回图中顶点的第一个邻接顶点 FirstAdjVert(graph,v) */
Vertex FirstAdjVert(LGraph graph, Vertex v) {
    Vertex u;

    if (v < graph->n_verts && graph->ver_list[v]->adj != NULL) {
        u = graph->ver_list[v]->adj->dest;
    } else {
        u = NIL;
    }
    return u;
}
/* 算法7-7 结束 */

/* 算法7-8: 判断边是否存在  ExistEdge(graph, u, v) */
bool ExistEdge(LGraph graph, Vertex u, Vertex v) {
    Position p;
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        p = graph->ver_list[u]->adj;
        while (p != NULL && p->dest != v) {
            p = p->next;
        }
        if (p != NULL) {
            ret = true;
        }
    }
    return ret;
}
/* 算法7-8 结束 */

/* 算法7-9: 向图中插入边 InsertEdge(graph, u,v,weight) */
void InsertEdge(LGraph graph, Vertex u, Vertex v, GElemSet weight) {
    Position p;

    if (ExistEdge(graph, u, v) == false) {
        p = (Position)malloc(sizeof(struct EdgeNode));
        p->dest = v;
        p->weight = weight;
        p->next = graph->ver_list[u]->adj;
        graph->ver_list[u]->adj = p;
        graph->m_edges++;
        if (graph->directed ==
                    false) { /* 如果是无向图，还要将u插入v的边表中 */
            p = (Position)malloc(sizeof(struct EdgeNode));
            p->dest = u;
            p->weight = weight;
            p->next = graph->ver_list[v]->adj;
            graph->ver_list[v]->adj = p;
        }
    }
}
/* 算法7-9 结束 */

/* 算法7-10: 从图中删除顶点及所有邻接于该顶点的边 RemoveVert(graph,v) */
void RemoveVert(LGraph graph, Vertex v) {
    int n, count;
    Vertex u, last_v;
    Position p, next_p;

    n = graph->n_verts;
    if (v < 0 || v >= n) {
        printf("错误：待删除的顶点不存在。\n");
    } else {
        count = 0; /* count计数与顶点v邻接的边的条数 */
        p = graph->ver_list[v]->adj; /* 删除由顶点v射出的边 */
        while (p != NULL) {
            next_p = p->next;
            free(p);
            count++;
            p = next_p;
        }
        graph->ver_list[v]->adj = NULL;
        for (u = 0; u < n; u++) { /* 删除射入顶点v的边 */
            p = graph->ver_list[u]->adj;
            if (p != NULL) { /* 非空链表 */
                if (p->dest == v) { /* 首结点为射入顶点v的边 */
                    graph->ver_list[u]->adj = p->next;
                    free(p);
                    count++;
                } else { /* 非首结点 */
                    while (p->next != NULL && p->next->dest != v) { /* 找到射入顶点v的边 */
                        p = p->next;
                    }
                    if (p->next != NULL) { /* 找到<u,v>这条边，删除 */
                        next_p = p->next;
                        p->next = next_p->next;
                        free(next_p);
                        count++;
                    }
                }
            }
        }
        last_v = n - 1; /* 最后一个顶点的编号 */
        for (u = 0; u < last_v;
                u++) { /* 将原来射入最后一个顶点的边都更新编号为v */
            p = graph->ver_list[u]->adj;
            while (p != NULL && p->dest != last_v) { /* 找到射入顶点v的边 */
                p = p->next;
            }
            if (p != NULL) { /* 将原来射入最后一个顶点的边都更新编号为v */
                p->dest = v;
            }
        }
        graph->ver_list[v] =
            graph->ver_list[last_v]; /* 顶点表中最后一个顶点移到位置v */
        if (graph->directed == false) { /* 无向图实际删除的边数要减半 */
            count >>= 1;
        }
        graph->m_edges -= count; /* 更新边的条数 */
        graph->n_verts--; /* 更新顶点个数 */
    }
}
/* 算法7-10 结束 */